package cn.camel.algorithm.rope.hash;

import java.util.Collection;
import java.util.List;
import java.util.Map;
import java.util.Set;

/**
 * @author: Camel
 * @description: 自定义HashMap
 * @date: 2025/10/14 14:31
 */
public class MyHashMap<K, V> {
    private static final int DEFAULT_CAPACITY = 16;
    private static final double LOAD_FACTOR = 0.75;

    private HashNode<K, V>[] table;
    private int size;

    @SuppressWarnings("unchecked")
    public MyHashMap() {
        table = new HashNode[DEFAULT_CAPACITY];
        size = 0;
    }

    // 哈希函数
    private int hash(K key) {
        return Math.abs(key.hashCode()) % table.length;
    }

    // 插入键值对
    public void put(K key, V value) {
        if (key == null) throw new IllegalArgumentException("Key cannot be null");

        int index = hash(key);
        HashNode<K, V> current = table[index];

        // 检查键是否已存在
        while (current != null) {
            if (current.key.equals(key)) {
                current.value = value; // 更新值
                return;
            }
            current = current.next;
        }

        // 插入新节点到链表头部
        HashNode<K, V> newNode = new HashNode<>(key, value);
        newNode.next = table[index];
        table[index] = newNode;
        size++;

        // 检查是否需要扩容
        if ((double)size / table.length > LOAD_FACTOR) {
            resize();
        }
    }

    // 获取值
    public V get(K key) {
        int index = hash(key);
        HashNode<K, V> current = table[index];

        while (current != null) {
            if (current.key.equals(key)) {
                return current.value;
            }
            current = current.next;
        }
        return null; // 键不存在
    }

    // 扩容
    @SuppressWarnings("unchecked")
    private void resize() {
        HashNode<K, V>[] oldTable = table;
        table = new HashNode[oldTable.length * 2];
        size = 0;

        for (HashNode<K, V> head : oldTable) {
            HashNode<K, V> current = head;
            while (current != null) {
                put(current.key, current.value);
                current = current.next;
            }
        }
    }

    public int size() { return size; }
    public boolean isEmpty() { return size == 0; }

    /**
     * @author: Camel
     * @description: 链地址法,每个数组位置存储一个链表，冲突元素添加到链表中.
     * @date: 2025/10/14 14:46
     */
    public class HashNode<K, V> {
        K key;
        V value;
        HashNode<K, V> next;

        public HashNode(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }
}
